\documentclass[a4paper,14pt,titlepage]{extarticle}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[left=20mm,right=15mm,top=20mm,bottom=20mm,bindingoffset=0cm]{geometry}
%left 20..30, right 10..15
\renewcommand{\baselinestretch}{1.5} % 1.5 .. 2.0
%font height >=1.8, 2.5 .. 2.7
\usepackage{tocloft}
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}

\def \usu {Федеральное агентство по образованию РФ \\
Государственное образовательное учреждение высшего профессионального образования \\
Уральский государственный университет им. А.М.Горького \\
Математико-механический факультет \\
Кафедра алгебры и дискретной математики}
\def \title {Программный комплекс для вычисления скоростей роста языков, избегающих экспоненты}
\def \author {Самсонов Алексей Валерьевич}
\def \authora {Самсонова Алексея Валерьевича}
\def \date {Екатеринбург \\ 2009}
\def \supergrade {кандидат физ.--мат. наук, доцент}
\def \super {Шур Арсений Михайлович}
\def \spec {Направление 010200 --- <<Математика. Прикладная математика>>}
\def \grade {Диссертация на соискание академической степени бакалавра физико-математических наук}
\def \work {Квалификационная работа на\\ степень бакалавра наук по направлению\\ 
<<Математика. Прикладная математика>>
}
\def \studenta {студента группы Мт-401}

\begin{document}
\begin{titlepage}\begin{center}
\small \usu\\
\vfil
\Large {\bf \title}\\
\small
%\LARGE \title\\
%\small \spec\\
%\small \grade\\
\vfil
\begin{tabular}{cc}
{
\begin{minipage}[]{250pt}
<<Допущен к защите>>\\
\line(1,0){116} \\
<<\line(1,0){16}>>\ \line(1,0){84}\  2009 г.
\end{minipage}
} &
\begin{minipage}[]{250pt}
\small
\work\\
\studenta\\
\authora\\  \newline
Научный руководитель:\\
\super\\
\supergrade\\
\end{minipage}
\end{tabular}
\vfil
\normalsize \date
\vfilneg
\end{center}\end{titlepage}

\setcounter{page}{2}
\centerline{\bf Реферат}\par\vskip 0.7cm
Темой квалификационной работы является описание алгоритма вычисления верхних и нижних оценок индексов роста языков, избегающих экспоненты. Работа занимает 38 страниц, содержит 2 таблицы и 4 приложения. В списке литературы содержится 6 наименований.

{\bf Ключевые слова}: индекс роста, избегаемость, регулярный язык, конечный антисловарь, распознающий автомат.

Объектом данного исследования являются языки, избегающие экспоненты и некоторые шаблоны. Целью исследования является создание эффективной реализации алгоритма вычисления оценок индексов роста этих языков. В данной работе приведено краткое описание алгоритма и способов улучшения его производительности. С помощью написанной программы получено множество оценок индексов роста языков и обнаружены закономерности, которым подчиняются автоматы, распознающие приближения этих языков.


\newpage

\renewcommand{\contentsname}{Оглавление}
\tableofcontents

\newpage
\section{Введение}
\label{section:intro}

В данной работе рассматривается алгоритм вычисления верхних и нижних оценок индексов роста нерегулярных языков, избегающих некоторые шаблоны или экспоненты (подробное описание и доказательство корректности работы алгоритма представлено в \cite{shur_algo}). Изучение таких языков является одной из центральных тем в комбинаторике слов: ещё в 1906 году Туэ показал (\cite{thue}), что квадраты избегаемы над тернарным алфавитом, а кубы ~--- над бинарным. Однако до недавнего времени не существовало универсального способа проверки избегаемости экспонент и шаблонов и способа вычисления оценок индексов роста языков, избегающих экспоненты.

Представленный алгоритм основан на следующей идее: вместо бесконечного антисловаря какого-либо нерегулярного языка строится конечное приближение этого антисловаря. Далее вычисляется индекс роста регулярного языка, заданного этим приближением. Полученный индекс роста будет являться верхней оценкой индекса роста исходного языка. Наконец, с помощью теорем, приведённых в \cite{shur_lower}, по верхней оценке строится и нижняя оценка. Чем больше будет конечное приближение антисловаря, тем точнее получатся оценки, поэтому чрезвычайно важную роль играет вопрос эффективности этого алгоритма.

В данной работе помимо непосредственно алгоритма рассматривается множество различных оптимизаций, направленных как на уменьшение времени работы программы, так и на сокращение объёма используемой памяти. Последнее особенно важно, так как чаще всего именно память является критическим ресурсом при компьютерных исследованиях больших автоматов. Практической целью этой работы было создание программы, реализующей данный алгоритм, которая позволяла бы вычислять (с точностью до нескольких знаков после запятой) оценки индексов роста для достаточно большого множества нерегулярных языков, используя при этом умеренное количество вычислительных ресурсов (например, предоставляемое обычным персональным компьютером). В качестве языка программирования был выбран язык С++.

В разделе \ref{section:theory} изложены основные понятия, определения и факты, используемые в данной работе.

Следующие три раздела соотвествуют основным этапам работы рассматриваемого алгоритма:
\begin{itemize}
\item построение конечного антисловаря, приближающего исходный антисловарь (раздел \ref{section:antidict}).
\item построение по антисловарю детерминированного конечного автомата, распознающего язык, заданный этим антисловарём (раздел \ref{section:dfa}).
\item вычисление индекса роста языка по распознающему автомату (раздел \ref{section:grate}).
\end{itemize}

Наконец, в разделе \ref{section:results} приводятся некоторые численные результаты и закономерности, полученные с помощью программы, реализующей указанный алгоритм.

%введение\\ ok
%Актуальность\\ ok
%Новизна и обзор\\
%Цели и задачи\\ ok
%Объёкт и предмет исследования\\ ok
%Методы\\ ok
%Структура работы\\ ok

\newpage
\section{Основные понятия и определения}
\label{section:theory}

Все рассматриваемые нами языки являются \textit{факториальными}, то есть, замкнутыми относительно взятия подслов. Мы будем называть слово $w$ \textit{запрещённым} в языке $L$, если оно не является подсловом никакого слова из $L$. \textit{Антисловарём} языка $L$ мы будем называть множество $M$, состоящее из всех минимальных (относительно взятия подслов) запрещённых в $L$ слов. Можно показать, что антисловарь строится по языку однозначно,
и, обратно, каждый антисловарь однозначно задаёт некоторый язык.

%Для языка $L$ над алфавитом $\Sigma$ и соответствующего ему антисловаря $M$ верны следующие равенства:
%$L=\Sigma^* - \Sigma^* M \Sigma^*, M=\Sigma L\cap L\Sigma\cap(\Sigma^*-L)$.
%Таким образом, каждый антисловарь однозначно задаёт некоторый язык.

\textit{Экспонентой} слова мы будем называть отношение длины слова к его минимальному периоду. Данная работа посвящена языкам с ограничением на экспоненту. Так, мы будем называть язык над алфавитом $\Sigma$ $\beta$-свободным ($\beta+$-свободным), если он состоит из всех слов из $\Sigma^*$, экспоненты всех подслов которых меньше $\beta$ (соответственно, не больше $\beta$).

Также нас будут интересовать языки, избегающие некоторые шаблоны. Например, язык над алфавитом $\Sigma$, избегающий шаблон $(XXY)^2$ ~--- это множество всех слов из $\Sigma^*$, ни одно подслово которых нельзя представить в виде $(XXY)^2$ для некоторых непустых слов $X$ и $Y$ из $\Sigma^*$.

\textit{Комбинаторной сложностью} языка $L$ над $\Sigma$ мы будем называть функцию $C_L(n)=|L\cap\Sigma^n|$, то есть, количество слов длины $n$, принадлежащих $L$. \textit{Индекс роста} $L$ определяется как $\alpha(L)=\limsup\limits_{n\to\infty}(C_L(n))^{1/n}$. Например, если $\alpha(L)=0$, то $L$ конечен, а если $\alpha(L)>1$, то $C_L(n)$ растёт экспоненциально.

Мы будем называть антисловарь $M_k$ \textit{k-приближением} антисловаря $M$, если он состоит из всех слов из $M$ длины не более $k$. Пусть $L_k$~--- язык, заданный антисловарём $M_k$. Тогда очевидно, что $M_1\subseteq \ldots\subseteq M_k\subseteq\ldots\subseteq M$ и \hbox{$L\subseteq\ldots\subseteq L_k\subseteq\ldots\subseteq L_1$}. А значит, индекс роста $L_k$ является верхней оценкой индекса роста $L$, причём $\lim\limits_{k\to\infty}\alpha(L_k) = \alpha(L)$.

Пусть $\phi: \Sigma \to \Sigma$ ~--- биекция, то есть, некоторая перестановка букв алфавита. Тогда $\phi$ однозначно продолжается на $\Sigma^*$. Заметим, что для любого слова $w\in\Sigma^*$ минимальные периоды $w$ и $\phi(w)$ совпадают, также $w$ и $\phi(w)$ одновременно удовлетворяют или не удовлетворяют некоторому шаблону. Мы будем называть два слова \textit{эквивалентными}, если существует перестановка букв алфавита, переводящая одно слово в другое. В рассматриваемом алгоритме в антисловарь добавляются только слова, лексикографически минимальные среди всех своих эквивалентов. По теореме из \cite{godsil}, индекс роста языка, заданного таким сокращённым <<антисловарём представителей>>, будет совпадать с индексом роста языка, заданного исходным антисловарём. Это позволит нам сократить и время работы программы, и объём используемой памяти примерно в $|\Sigma|!$ раз, что особенно важно для изучения языков над большими алфавитами.

Рассмотрим способы вычисления индекса роста языка, если нам известен распознающий автомат этого языка. Из этих способов вытекают алгоритмы, приведённые в разделе \ref{section:grate}. \textit{Индексом} ориентированного графа называют максимальное собственное значение его матрицы смежности (\textit{корень Фробениуса}). Заметим, что все распознающие автоматы, которые мы строим по антисловарям, являются достижимыми и кодостижимыми, и для них верно следующее утверждение: индексы роста языков, распознаваемых этими автоматами, совпадают с индексами соответствующих орграфов. Таким образом, рассматриваемый алгоритм приближённо вычисляет максимальное собственное значение матрицы смежности распознающего автомата.

Пусть $\alpha$~--- верхняя оценка индекса роста языка, избегающего экспоненту $\beta \geqslant 2$. Тогда в качестве нижней оценки индекса роста этого языка можно взять любое $\gamma$, для которого выполняется неравенство $\gamma + \frac{1}{{\gamma}^{(R-1)}(\gamma-1)} \leqslant \alpha$ (где $R$~--- ограничение на длину корня слов из антисловаря). Подробно способ получения этой оценки и её доказательство рассмотрены в \cite{shur_lower}. В разделе \ref{section:grate} описано, как с помощью этого неравенства мы вычисляем нижнюю оценку индекса роста. Это неравенство справедливо и для языка над бинарным алфавитом, который одновременно избегает пару шаблонов $(XXY)^2$ и $X^3$.

\newpage
\section{Построение антисловаря}
\label{section:antidict}

Приведём краткое описание алгоритма, который строит приближение антисловаря языка $L$ над алфавитом $\Sigma=\{0, 1 \ldots, n-1\}$, избегающим экспоненту $\beta$.

Рассмотрим слово $w\in\Sigma^*$, обозначим длину $w$ как $Len(w)$. Построим слово $u$ следующим образом: оно будет начинаться со слова $w$, иметь длину $\lceil Len(w)\cdot\beta \rceil$ и период $Len(w)$. Тогда слово $u$ лежит в антисловаре $M$ языка $L$ в том и только в том случае, если ни одно собственное подслово $u$ не лежит в $M$. Если $u \in M$, мы будем называть $w$ \textit{корнем} запрещённого слова $u$. В нашем алгоритме мы рассматриваем приближение антисловаря исходного языка, в котором длина корней слов из антисловаря не превосходит некоторого числа $R$. Напомним также, что мы строим антисловарь <<лексикографически минимальных представителей>> (см. раздел \ref{section:theory}).

Основные структуры данных:
\begin{itemize}
\item $Q$~--- очередь потенциальных корней слов из антисловаря. В частности, все слова в $Q$ не являются запрещёнными в $L$.
\item $T$~--- бор (trie), содержащий все построенные на данный момент слова из антисловаря. Бор является своеобразным остовным деревом автомата, распознающего язык, заданный антисловарём. Использование бора позволяет нам для любого слова $w$ проверять, принадлежит ли какой-нибудь префикс $w$ антисловарю, за время $O(Len(w))$.
\end{itemize}

Вспомогательные функции (см. приложение \ref{subsection:aux_ad}):
\begin{itemize}
\item $IsForbidden$($w$, $direction$)~--- Если $direction$ = $forward$ ($backward$), функция проверяет, лежит ли хотя бы один префикс (суффикс) слова $w$ в $M$. Проверку суффиксов можно также осуществлять за линейное время, поскольку экспонента слова не изменяется при прочтении его в обратном порядке. Также заметим, что префиксы (суффиксы) $w$ не обязательно являются минимальными представителями, однако функция на ходу строит эквивалентных этим префиксам (суффиксам) минимальных представителей и проверяет, лежат ли они в $T$.
\item $AddWord$($w$)~--- добавляет слово $w$ в бор $T$ за линейное время.
\end{itemize}

Приведём основную схему работы алгоритма:
\begin{verbatim}
01 Q.push("0");
02 while (Q.hasElements()){
03   w = Q.pop();
04   build u; // см. правила построения u выше
05   if (ни одно собственное подслово u не лежит в T)
06     AddWord(u);
07   if (Len(w) < R){ // строим новые потенциальные корни
08     for c = '0' to Min(MaxLetter(w)+1, n-1){
09       w2 = w + c;
10       if (ни одно подслово w2 не лежит в Т)
11         Q.push(w2);
12     }
13   }
14 }
\end{verbatim}

Теперь подробно рассмотрим реализацию данного алгоритма. Сперва обратимся к проверке в строке 5. Вспомним, что с помощью функции $IsForbidden$ мы можем проверить, лежит ли хотя бы один суффикс некоторого слова в боре $T$. Любое подслово $u$~--- суффикс некоторого префикса, поэтому достаточно запустить функцию $IsForbidden$ для каждого префикса $u$ с направлением $backward$. Однако, первые $Len(w)$ префиксов совпадают с префиксами $w$, которое не запрещено. Поэтому проверку можно начинать с префиксов длины $Len(w)+1$, а в конце дополнительно проверить суффикс слова $u$ длины $Len(u)-1$ с направлением $backward$ и префикс той же длины с направлением $forward$. Целесообразно перебирать префиксы в порядке возрастания длины: как только для одного из них $IsForbidden$ вернёт $true$, мы сразу сможем сделать вывод, что $u$ не лежит в антисловаре. Соответственно, проверку в строке 5 можно реализовать так:

\begin{verbatim}
bool ok = true;
for i = Len(w)+1 to Len(q)-1 {
  if (IsForbidden(u[1..i], backward)){
    ok = false; // слово u - не подходит
    break;
  }
}
if (ok) and (IsForbidden(u[2..Len(u)], backward)){
  ok = false;
}
if (ok) and (IsForbidden(u[1..Len(u-1)], forward)){
  ok = false;
}
\end{verbatim}

Обратимся к проверке в строке 10. Префикс $w2$ длины $Len(w2)-1$~--- это слово $w$, а значит, ни одно его подслово не лежит в $T$. Поэтому достаточно проверить только суффиксы слова $w2$, то есть запустить функцию $IsForbidden$ для слова $w2$ с направлением $backward$. Можно также заметить, что если мы дописываем букву с номером $MaxLetter(w)+1$, которой не было в слове $w$, то запрещенных подслов появится не может, и проверку в строке 10 можно не делать. Вспомним, что слово $w$ начинается с нуля, а значит, префикс слова $u$ длины $Len(w)+1$ заканчивается на ноль. Поэтому результат проверки этого префикса в строке 5 будет совпадать с результатом проверки слова $w2$ в строке 10 в случае $c = 0$. Значит, вместо запуска $IsForbidden$ в строке 10 при $c = 0$ можно взять результат первого запуска $IsForbidden$ в строке 5.

Наконец, заметим, что при $Len(w) = R-1$ слово $w2$ не имеет смысла добавлять в очередь, поскольку мы не будем строить из него новые корни. Вместо этого можно сразу запустить для $w2$ проверку из строки 5 и, при необходимости, добавить соответствующее запрещённое слово в $T$.

Поговорим о способе хранения двух ключевых в этой части программы структур данных: очереди $Q$ и бора $T$. При исследовании языков над большими (7 и более букв) алфавитами размер очереди играет критическую роль: в этом случае именно от эффективного (по объему используемой памяти) построения антисловаря зависит точность, с которой мы сможем посчитать оценки индексов роста. В написанной программе очередь представляет собой обычный циклический массив байт. Запись строк в очередь и чтение из неё производятся вручную: стандартные типы данных языка не используются для экономии памяти, которую будет занимать различная дополнительная информация. Помимо собственно строки в очереди не хранится никакой информации. В алгоритме потенциальные корни обрабатываются в порядке возрастания длины, и в каждый момент работы алгоритма длины всех строк в очереди отличаются не больше, чем на 1. Поэтому <<точка раздела>> между строками различной длины и длина текущего потенциального корня хранятся не в очереди, а в отдельных переменных. Также огромную роль в экономии памяти играет битовое кодирование: при размере алфавита, не превосходящем 4, в каждый байт записывается по 4 символа хранящихся строк, а, например, при размере, не превосходящем 16~--- по 2 символа (см. примечание \ref{subsection:bit_queue}). Бор $T$ хранится в таблице, которая в дальнейшем будет использоваться для хранения распознающего автомата (см. раздел \ref{section:dfa}). Занумеруем вершины автомата числами от $0$ до $m-1$, а буквы алфавита~--- числами от $0$ до $n-1$. Тогда если $v$~--- номер вершины автомата, а $c$ - буква, то в элементе таблицы dfa[$v$][$c$] хранится номер вершины, в которую осуществляется переход из вершины $v$ по букве $c$. Поскольку мы работаем с большими автоматами, на хранение каждого элемента таблицы отводится 4 байта. Отметим, что поскольку память для хранения автомата выделяется динамически, а мы заинтересованы в быстрой работе с автоматом и хотим уменьшить фрагментацию памяти до минимума, <<таблица>> на самом деле представляет собой одномерный массив из $mn$ элементов, а элемент dfa[$v$][$c$] хранится в ячейке dfa[$vn+c$].

Использование большой очереди и поиска в ширину вместо рекурсивного перебора позволяет нам быстро строить антисловари для достаточно больших значений $R$, поскольку при проверке очередного слова мы уже знаем все запрещённые слова меньшей длины. Однако, в условиях, когда память является наиболее важным ресурсом, может быть оправданно пожертвовать временем работы программы, сэкономив память. Например, иногда имеет смысл перебирать последние несколько символов потенциального корня рекурсивно, без использования очереди. В этом случае самые большие подслова потенциальных слов из антисловаря мы проверяем не с помощью функции $IsForbidden$, а простым прямолинейным алгоритмом. Несмотря на кажущуюся неэффективность этой модификации, она позволяет несколько улучшить получаемые оценки. Например, рассмотрим $8/7+$-свободный язык над алфавитом из 8 символов и длиной корня не более 80. При переборе в глубину трёх последних символов корня программа работает на 33\% дольше, но объем используемой очереди при этом уменьшается в два раза.

Алгоритм, описанный в этой работе, применим не только для языков, избегающих экспоненты. С его помощью можно посчитать индекс роста любого языка, заданного антисловарём. При этом построение распознающего автомата (см. раздел \ref{section:dfa}) и вычисление индекса роста (см. раздел \ref{section:grate}) менять не требуется, достаточно лишь реализовать алгоритм построения соответствующего антисловаря. Например, с помощью рассматриваемой программы были проведены исследования языков над бинарным алфавитом, избегающих шаблоны $(XXY)^2$ и $(XYX)^2$. Построение антисловаря в этих случаях также основано на очереди потенциальных корней: слов, которые могут принять вид $XXY$ или $XYX$. При этом, в первом случае необходимо дополнительно хранить в очереди информацию о том, является ли слово квадратом и есть ли у него собственный префикс-квадрат, а во втором случае требуется хранить список всех периодов слова. Похожим образом устроен алгоритм построения антисловаря языка, избегающего одновременно шаблоны $(XXY)^2$ и $X^3$, и языка, избегающего одновременно шаблоны $(XYX)^2$ и $X^3$. Для всех этих языков были получены некоторые оценки индексов роста, которые приведены в разделе \ref{section:results}.
  
  
  
 
\newpage
\section{Построение автомата}
\label{section:dfa}

В этом разделе мы обращаемся к алгоритму, который по бору $T$, содержащему антисловарь некоторого языка, строит детерминированный конечный автомат $A$, распознающий этот язык. Этот алгоритм основан на классическом алгоритме Ахо-Корасик \cite{aho}, строящем автомат для поиска одного из элементов словаря в тексте. Подробное описание и обоснование используемого нами алгоритма можно найти в \cite{shur_algo}. Алгоритм работает эффективно~--- обработка каждой вершины автомата производится за $O(|\Sigma|)$ в среднем и за $O(|\Sigma|{\cdot}\log |V|)$ (где $|V|$~--- количество вершин в автомате) в худшем и достаточно редком случае. Таким образом, время построения автомата мало по сравнению с временем построения антисловаря (см. раздел \ref{section:antidict}) и с временем вычисления индекса роста (см. раздел \ref{section:grate}). При написании программы сам алгоритм не модифицировался, но при этом использовались различные техники, направленные на уменьшение объема используемой памяти. Поэтому мы не будем приводить подробное описание алгоритма, а укажем лишь вспомогательные структуры данных, использующиеся в нём.

Напомним, что каждой вершине $u$ бора $T$ можно поставить в соответствие слово, которое прочитывается по пути от корня бора до $u$. В обычном алгоритме Ахо-Корасик \textit{функция отката} $f(u)$ обозначает вершину, соответствующую максимальному собственному суффиксу слова для вершины $u$, который также можно прочитать в боре. В представленном алгоритме ситуация сложнее: этот собственный суффикс может не быть лексикографически минимальным в своём классе эквивалентности. Поэтому вводится функция $lf(u)$, которая обозначает вершину, соответствующую лексикографически минимальному эквиваленту этого суффикса. Также $\sigma(u)$ обозначает частичную перестановку $\Sigma$, переводящую $f(u)$ в $lf(u)$. Для каждой вершины мы дополнительно храним символ $last[u]$, которым помечено ребро из отца $u$ в $u$, и массив маркеров $back[u]$, который для каждого из $|\Sigma|$ исходящих рёбер указывает, являтся ли оно прямым или обратным в боре. Наконец, вершины должны обрабатываться в порядке обхода в ширину, начиная с корня, поэтому потребуется также очередь для хранения вершин.

Итак, в алгоритме используются следующие структуры данных:
\begin{itemize}
\item Бор $T$, который мы достраиваем до распознающего автомата $A$;
\item Очередь для поиска в ширину;
\item Массив $lf[u]$, значения~--- от 0 до $|V|-1$;
\item Массив $last[u]$, значения~--- от 0 до $|\Sigma|-1$;
\item Двумерный массив $\sigma[u][c]$, где $c$ и значения~--- от 0 до $|\Sigma|-1$;
\item Двумерный массив $back[u][c]$, где $c$~--- от 0 до $|\Sigma|-1$, значения~--- 0 или 1;
\end{itemize}

В программе реализована следующая упаковка данных. Заметим, что размер очереди для поиска в ширину можно сделать равным удвоенному максимальному количеству вершин на уровне бора. Это количество можно оценить сверху количеством слов в антисловаре, которое заметно меньше количества вершин в боре. Поэтому объёмом памяти, необходимым для хранения очереди, можно пренебречь. Мы рассматриваем алфавиты, состоящие не более чем из 15 символов. Предполагая, что размер автомата не превосходит $2^{28}$ вершин, на хранение $lf[u]$ и $last[u]$ можно в сумме выделить 4 байта. Для хранения массива флагов $back[u]$ требуется $|\Sigma|$ бит, то есть, не больше 2 байт. В зависимости от размера алфавита для каждой вершины $u$ на хранение соответствующего ей массива $back[u]$ выделяется 4, 8 или 16 бит. Аналогично, для каждой вершины $u$ на хранение соответствующего ей массива $\sigma[u]$ выделяется $\lceil \frac{|\Sigma|}{2} \rceil$ байт, а в каждом байте хранятся значения $\sigma(u,c1)$ и $\sigma(u,c2)$ для разных $c1$ и $c2$. Наконец, для уменьшения фрагментации и более быстрой работы двумерные массивы $back$ и $\sigma$ свёрнуты в одномерные аналогично массиву, задающему бор (представление в памяти бора $T$ описано в разделе \ref{section:antidict}). Достраивая бор до автомата $A$, мы лишь записываем некоторые значения в соответствующий массив.

Таким образом, мы рассмотрели реализацию эффективного алгоритма постоения распознающего автомата по бору, в которой для каждой вершины автомата выделяется не более $(6 + \lceil \frac{|\Sigma|}{2} \rceil)$ байт дополнительной памяти.

\newpage
\section{Вычисление индекса роста}
\label{section:grate}

В разделе \ref{section:theory} указано, что индекс роста можно вычислить как максимальное собственное значение матрицы смежности распознающего автомата $A$. Если мы добавим петлю к каждой вершине $A$, то НОД длин всех орциклов станет равен единице. В этом случае мы попадём в условия теоремы из \cite{shur_algo}, и сможем вычислить индекс роста $\alpha$ как $\lim\limits_{n\to\infty}\frac{C_L(n+1)}{C_L(n)}$. При добавлении петли к каждой вершине индекс роста языка, распознаваемого автоматом, увеличивается на единицу (так как добавление петли эквивалентно добавлению единичной матрицы к матрице смежности орграфа). Легко понять, что $C_L(n)$~--- это в точности количество всевозможных путей длины $n$ из стартовой вершины в автомате $A$ (в нашем автомате все состояния являются терминальными, однако некоторые рёбра ведут в фиктивную нетерминальную вершину). Обозначим за $P_v(n)$ количество путей длины $n$, начинающихся в стартовой вершине и заканчивающихся в вершине $v$. Выпишем следующее соотношение: $P_v(n)=\sum P_u(n-1)+P_v(n-1)$, где сумма берётся по всем таким $u$, что $(u,v)$~--- ребро в исходном автомате, а дополнительное слагаемое соответствует добавленной петле. Таким образом, мы можем последовательно вычислять значения $C_L(n)$ и считать отношения $\frac{C_L(n+1)}{C_L(n)}$. Однако, возникают следующие проблемы:

\begin{itemize}
\item Неизвестно, когда значение $\frac{C_L(n+1)}{C_L(n)}$ станет достаточно близк\'{о} к реальному значению $\alpha$.
\item Даже если предполагать, что алгоритм достаточно устойчив к ошибкам округления, и считать значения $C_L(n)$ в 8-байтовом вещественном типе $double$, то для каждой вершины автомата потребуется выделить 16 байт на пару счётчиков.
\end{itemize}

Оказывается, существует почти столь же эффективный алгоритм вычисления индекса роста, в котором решена первая проблема, и который использует меньший объём памяти в среднем случае.

Во-первых, вспомним, что индекс орграфа равен максимальному индексу его компонент сильной связности. Разобьём граф распознающего автомата на компоненты сильной связности и посчитаем индекс каждой из них (индекс компоненты, состоящей из одной вершины, равен нулю, а индекс простого цикла~--- единице). Пусть $P_v(n)$~--- количество путей длины $n$ в некоторой компоненте сильной связности, начинающихся в любой вершине компоненты и заканчивающихся в вершине $v$. Тогда если НОД длин всех циклов компоненты равен единице (например, если мы добавили петлю к каждой её вершине), то индекс компонеты $\alpha = \lim\limits_{n\to\infty}\frac{P_v(n+1)}{P_v(n)}$, причём последовательность сходится с экспоненциальной скоростью. Более того, по теореме, приведённой в \cite{shur_algo}, для любого $n$ верны следующие неравенства: $\min\frac{P_v(n+1)}{P_v(n)} \leqslant \alpha \leqslant \max\frac{P_v(n+1)}{P_v(n)}$. Из этого факта мы получаем следующий алгоритм, вычисляющий индекс роста языка по его распознающему автомату с точностью $delta$ (это немного модифицированная версия алгоритма из \cite{shur_algo}):

\begin{verbatim}
(разбить A на компоненты сильной связности A_i);
for each A_i{
  if (A_i - одна вершина) ans_i = 0;
  else if (A_i - простой цикл) ans_i = 1;
  else{
    for each u in A_i{
      u.old = 1; // тип double
      u.new = 1; // тип double
    }
    while true{
      for each (u,v) in A_i{
        v.new = v.new + u.old;
      }
      minrate = min{u.new/u.old};
      maxrate = max{u.new/u.old};
      if (maxrate - minrate < 2*delta){
        ans_i = (minrate + maxrate)/2;
        break while;
      }
      for each u in A_i{
        u.old = u.new;
      }
    }
  }
}
return max{ans_i}
\end{verbatim}

На каждой итерации этого алгоритма производится $O(|V|+|E|)$ операций (где $|V|$~--- количество вершин в компоненте, а $|E|$~--- количество рёбер в ней). Отметим преимущества этого алгоритма:

\begin{itemize}
\item Мы можем определить итерацию, на которой получено достаточно точное значение индекса роста;
\item Алгоритм позволяет существенно сэкономить объем используемой памяти в том случае, если компоненты сильной связности малы. Действительно, заметим, что мы заводим счётчики $u.old$ и $u.new$ только для вершин, лежащих в нетривиальных компонентах. Также отметим, что во время вычисления индекса роста уже не обязательно хранить в памяти весь автомат $A$. Например, если компонента сильной связности одна, и её размер мал по сравнению с размером автомата, то выгодно заменить хранящийся в памяти автомат на список рёбер, лежащих в этой компоненте, освободив таким образом большое количество памяти под счётчики. Как указано в разделе \ref{section:results}, именно этот случай практически всегда имеет место при малых экспонентах.
\end{itemize}

Таким образом, у нас есть алгоритм, способный достаточно быстро вычислять индекс роста языка по распознающему автомату, разбитому на компоненты сильной связности. Осталось рассмотреть эффективный способ нахождения этого разбиения. Классический алгоритм, использующий поиск в глубину в исходном и транспонированном графе, в данном случае применять невыгодно, поскольку построение транспонированного графа требует выделения большого количества памяти. Поэтому мы воспользуемся алгоритмом Тарьяна, изложенным в \cite{tarjan}. Алгоритм обходит граф в глубину. Компоненты сильной связности являются поддеревьями в дереве поиска в глубину. Корни этих поддеревьев назовём корнями компонент сильной связности. Пусть $T[v]$~--- номер вершины в порядке обхода в глубину, а $Z[v] = \min\{T[u]: u$ достижимо из $v, v$ достижимо из $u\}$. Тогда вершина $v$~--- корень компоненты сильной связности в том и только в том случае, если $Z[v] = T[v]$. Помимо массивов $Z$ и $T$ в алгоритме также используется стек для вершин $S$, в который вершины добавляются в порядке их обнаружения. Если вершина $v$~--- корень компоненты, то все вершины, лежащие в стеке выше $v$, принадлежат этой компоненте. Они удаляются из стека, и алгоритм продолжает работу. Поскольку все вершины нашего автомата достижимы из начальной вершины, достаточно запустить из неё следующую рекурсивную процедуру.

\begin{verbatim}
Инициализация:
S = empty;
time = 1;
для всех v: T[v] = 0;

Tarjan(v){
  T[v] = time; // время входа
  Z[v] = time;
  time = time+1;
  S.push(v);
  for each (v, u) in A{
    if (T[u] = 0){ // не посещена
      Tarjan(u);
      Z[v] = min(Z[v], Z[u]); 
    }
    else if (u in S){ // u, v достижимы друг из друга
      Z[v] = min(Z[v], Z[u]);
    }
  }
  if (T(v) = Z(v)){ // корень компоненты
    new_scc = empty;
    do{
      u = S.pop();
      new_scc.push(u);
    } while (u != v);
    out(new_scc); // очередная компонента
  }
}
\end{verbatim}

Однако, нас интересует нерекурсивная реализация этого алгоритма, поскольку программный стек достаточно сильно ограничен, к тому же при рекурсивной реализации большое количество памяти будет тратиться на хранение временных переменных. Для нерекурсивной реализации нам понадобится массив $father$, в котором мы будем хранить непосредственных предков вершин в дереве поиска в глубину, и массив $cnt$, в котором мы будем хранить количество обработанных соседей каждой вершины. Заметим, что мы можем модифицировать исходный алгоритм, заменив массив $Z$, в котором хранятся достаточно большие числа, на массив маркеров $modified$. Значение $modified[v] = true$, если значение $T[v]$ хотя бы раз уменьшалось. Наконец, предположим, что в распознающем автомате есть ровно одна нетривиальная компонента сильной связности. Покажем, что в этом случае мы можем хранить не весь стек $S$, а лишь массив маркеров $instack$ ($instack[v] = true$, если $v$ лежит в стеке). Действительно, пусть $v$~--- какая-нибудь вершина этой компоненты (её можно найти нерекурсивным поиском в глубину, см. примечание \ref{subsection:dfs_tarjan}). Запустим процедуру $Tarjan(v)$. Тогда если $Z[u] = T[u]$ и $u \neq v$, то $u$~--- корень компоненты сильной связности, и эта компонента вырожденная (состоит только из вершины $u$). Установив $instack[u] = false$, мы промоделируем удаление $u$ из стека. После того, как алгоритм завершит свою работу, определить все вершины, лежащие в единственной компоненте сильной связности, несложно: это вершина $v$ и все такие вершины $u$, для которых $modified[u] = true$. Приведём псевдокод этого алгоритма:


\begin{verbatim}
Инициализация:
time := 1;
для всех v:
T[v] = cnt[v] = 0;
instack[v] = modified[v] = false;

cur - вершина, лежащая в компоненте сильной связности
father[cur] = -1;

while (cur != -1){
  if (cnt[cur] = 0){ // начинаем обработку вершины
    T[cur] = time;
    time = time + 1;
    instack[cur] := true;
  }
  else{ // пытаемся обновить T через сына
    prev = dfa[cur][cnt[cur]-1];
    if (prev >= 0) and (father[prev] = cur) and (T[prev] < T[cur]){
      T[cur] = T[prev];
      improved[cur] = true;
    }
  }
  if (cnt[cur] = ALPHABET_SIZE){ // уже обработали всех соседей
    if (improved[cur] = false){ // достать из стека
      instack[cur] = false;
    }
    cur = father[cur]; // вернуться к отцу
  }
  else{
    nxt = dfa[cur][cnt[cur]]; // взять очередного соседа
    cnt[cur] = cnt[cur] + 1;
    if (nxt >= 0){ // ребро существует
      if (T[nxt] = 0){ // новая вершина
        father[nxt] = cur;
        cur = nxt;
      }
      else if (instack[nxt]) and (T[nxt] < T[cur]){ // обновляем T
        T[cur] = T[nxt];
        improved[cur] = true;
      }
    }
  }
}
\end{verbatim}

Теперь заметим, что большие значения принимают только элементы массивов $T$ и $father$. Для хранения элементов $T[v]$ и $father[v]$ выделим по 4 байта, а все остальные числа и маркеры ($cnt[v]$, $instack[v]$, $modified[v]$) упакуем в 1 байт. Таким образом, мы разработали эффективный алгоритм поиска единственной компоненты сильной связности в графе, который использует 9 байт дополнительной памяти для каждой вершины.

Рассмотрим, как с помощью неравенства, приведённого в разделе \ref{section:theory}, в алгоритме строится значение нижней оценки. Пусть $\alpha$~--- верхняя оценка индекса роста языка. В \cite{shur_lower} показано, что у функции $f(\gamma) = \gamma + \frac{1}{{\gamma}^{(R-1)}(\gamma-1)}$ (где $R$~--- ограничение на длину корня слов из антисловаря) есть единственный минимум на интервале $(1,\alpha)$. Этот минимум мы найдём с помощью троичного поиска. Пусть минимум достигается в точке $x$. Тогда если $f(x) \ge \alpha$, то нижнюю оценку получить нельзя. В противном случае у функции $(f(\gamma)-\alpha)$ есть единственный ноль на интервале $(x,\alpha)$. Этот ноль мы найдём с помощью двоичного поиска. Итак, если ноль достигается в точке $z$, то $z$ и является нижней оценкой индекса роста исследуемого языка. Ниже приведён псевдокод описанного алгоритма:

\begin{verbatim}
double f(gamma){
  return gamma + 1.0 / pow(gamma, R-1) / (gamma - 1);
}

double get_mrate(double grate){ // grate - верхняя оценка
  l = 1;
  r = grate;
  while (r - l > delta){
    // разбиваем отрезок на три части
    p = (2*l + r) / 3;
    q = (l + 2*r) / 3;
    // и исключаем левую или правую треть
    if (f(p) < f(q)) r = q;
    else l = p;
  }
  x = (l+r)/2;
  if (f(x) >= grate){ // оценку построить нельзя
    return 0;
  }
  l = x;
  r = grate;
  // метод деления отрезка пополам
  while (r - l > delta){
    q = (l+r) / 2;
    if (f(q) < grate) l = q;
    else r = q;
  }
  return (l+r)/2;
}
\end{verbatim}

Поскольку троичный и двоичный поиски работают за логарифмическое время, вычисление нижней оценки осуществляется достаточно быстро, дополнительная память также не используется.

\newpage
\section{Результаты экспериментов}
\label{section:results}

Программа, реализующая описанный алгоритм и использующая указанные оптимизации, запускалась на большом количестве различных входных данных. Тестирование проводилось на персональном компьютере с процессором Intel Core 2 Duo 2.33GHz и 2 Гб оперативной памяти. Избранные результаты приведены в Таблице \ref{table:exp}.

Автоматы, распознающие приближения исследуемых языков, подчиняются следующим закономерностям:

\begin{itemize}
\item Во всех построенных автоматах была ровно одна нетривиальная компонента сильной связности. Именно поэтому интерес представляет модификация алгоритма Тарьяна, использующая меньше памяти в этом случае (см. раздел \ref{section:grate}).
\item НОД длин циклов компоненты сильной связности почти во всех автоматах равен 1. В этом случае мы можем не добавлять петлю к каждой вершине в алгоритме вычисления верхней оценки индекса роста. Этот результат важен, поскольку алгоритм в этом случае быстрее находит ответ.
\item Размер компоненты сильной связности увеличивается с ростом экспоненты. Это означает, что для маленьких экспонент выделение компоненты сильной связности и хранение списка рёбер компоненты вместо всего автомата даёт существенный выигрыш в производительности и позволяет получать оценки индексов роста для очень больших автоматов (до 100 миллионов вершин), компонента сильной связности которых мала.
\item Размер очереди играет критическую роль при исследовании языков над большими алфавитами в случае маленьких экспонент. В этом случае распознающий автомат получается сравнительно небольшой, однако для его построения требуется проверить много длинных потенциальных корней. Также размер очереди критичен для исследования $7/5+$-свободного языка над алфавитом из 4 символов. Во всех остальных случаях алгоритм использовал наибольшее количество памяти при вычислении верхней оценки индекса роста, так как на этом этапе нужно для каждой вершины компоненты сильной связности хранить пару счётчиков.
\item Дольше всего алгоритм работает для языков, избегающих малую экспоненту. В этом случае время в основном тратится на построение антисловаря (для больших алфавитов), или на вычисление индекса роста (в случае небольших алфавитов очень велико количество итераций). Эти два фактора сочетаются при исследовании $7/5+$-свободного языка над алфавитом из 4 символов.
\item Представляет интерес поведение индекса роста языка, избегающего экспоненту $\beta$, как функции от $\beta$ (при фиксированном размере алфавита). Из проведённых экспериментов можно сделать предположение о том, что функция $\alpha(\beta)$ для алфавита размера $n \ge 3$ имеет скачки, большие единицы, в точках $\frac{n-1}{n-2}, \frac{n-2}{n-3}, \ldots 2$.
\end{itemize}

\begin{table}[!htb]
\caption{\sl Оценки индексов роста языков, избегающих экспоненты. Столбцы содержат следующую информацию (слева направо): размер алфавита, запрещённая экспонента, максимальная длина корня, размер очереди (в символах), размер антисловаря, размер автомата, размер компоненты сильной связности, количество итераций, нижняя оценка, верхняя оценка.}
\label{table:exp}

\vspace*{5pt}
\tabcolsep=3pt

\centerline{
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
$|\Sigma|$ & $\beta$ & $R$ & $|Q|$ & $|M|$ & $|V|$ & $|{V}_{scc}|$ & $\bar{n}$ & $\gamma$ & $\alpha$ \\
\hline
2 & 7/3+ & 64 & 112\,081\,412 & 972\,747 & 79\,301\,398 & 22\,187\,707 & 387 & 1.220623 & 1.220645 \\
\hline
2 & 3 & 36 & 26\,579\,702 & 1\,241\,239 & 83\,006\,914 & 44\,649\,350 & 211 & 1.457573 & 1.457577 \\
\hline
2 & 3+ & 24 & 11\,757\,234 & 1\,414\,760 & 64\,323\,422 & 53\,916\,317 & 136 & 1.795125 & 1.795126 \\
\hline
2 & 4+ & 19 & 1\,328\,870 & 253\,420 & 13\,560\,908 & 12\,665\,988 & 123 & 1.920793 & 1.920802 \\
\hline
3 & 7/4+ & 65 & 349\,468\,802 & 1\,339\,611 & 68\,724\,314 & 20\,346\,018 & 335 & --- & 1.245610 \\
\hline
3 & 2 & 54 & 132\,116\,494 & 1\,112\,717 & 59\,890\,073 & 21\,407\,525 & 267 & 1.301759 & 1.301762 \\
\hline
3 & 2+ & 17 & 18\,024\,610 & 3\,189\,542 & 54\,730\,037 & 52\,752\,774 & 81 & 2.605879 & 2.605879 \\
\hline
4 & 7/5+ & 191 & 2\,244\,605\,660 & 187\,948 & 19\,586\,549 & 1\,629\,544 & 3431 & --- & 1.069527 \\
\hline
4 & 2 & 18 & 20\,234\,405 & 2\,306\,512 & 40\,581\,402 & 39\,210\,704 & 70 & 2.621508 & 2.621508 \\
\hline
4 & 2+ & 13 & 4\,296\,194 & 1\,532\,902 & 20\,583\,499 & 20\,136\,292 & 56 & 3.728494 & 3.728494 \\
\hline
5 & 4/3 & 100 & 1\,325\,703\,058 & 287\,622 & 15\,190\,168 & 2\,904\,075 & 449 & --- & 1.164632 \\
\hline
5 & 4/3+ & 23 & 131\,689\,428 & 2\,543\,208 & 23\,613\,749 & 20\,859\,902 & 96 & --- & 2.249056 \\
\hline
5 & 3/2 & 22 & 121\,979\,342 & 3\,588\,828 & 42\,681\,448 & 39\,882\,089 & 79 & --- & 2.402445 \\
\hline
5 & 3/2+ & 16 & 39\,272\,252 & 5\,903\,234 & 52\,408\,053 & 50\,871\,961 & 59 & --- & 3.492828 \\
\hline
5 & 2 & 14 & 4\,682\,641 & 1\,160\,529 & 15\,889\,694 & 15\,560\,907 & 52 & 3.732539 & 3.732539 \\
\hline
5 & 2+ & 12 & 3\,136\,146 & 1\,549\,785 & 19\,465\,201 & 19\,124\,667 & 49 & 4.789851 & 4.789851 \\
\hline
5 & 3+ & 11 & 816\,302 & 489\,283 & 10\,865\,802 & 10\,762\,621 & 50 & 4.966241 & 4.966241 \\
\hline
7 & 7/6+ & 83 & 2\,424\,341\,380 & 54\,114 & 2\,239\,313 & 644\,315 & 287 & --- & 1.236948 \\
\hline
9 & 9/8+ & 83 & 2\,665\,382\,282 & 3\,055 & 149\,203 & 45\,928 & 350 & --- & 1.246682 \\
\hline
12 & 12/11+ & 78 & 486\,146\,047 & 160 & 4\,632 & 2\,370 & 376 & --- & 1.242879 \\
\hline
15 & 15/14+ & 75 & 147\,881\,602 & 806 & 15\,637 & 8\,899 & 456 & --- & 1.241838 \\
\hline
\end{tabular}
}
\end{table}

\newpage
Также были проведены исследования языков над бинарным алфавитом, избегающих шаблоны $(XXY)^2$ и $(XYX)^2$. Верхние оценки индексов роста этих языков оказались близки друг к другу и достаточно велики (см. Таблицу \ref{table:xxy}). Достаточно интересные результаты получаются при рассмотрении избегаемости каждого из этих шаблонов вместе с шаблоном $X^3$. Правило построения антисловаря в обоих случаях практически не изменяется (более того, в обоих случаях шаблон $X^3$ добавляет в антисловарь лишь два слова). Можно также показать, что для этих языков применим описанный в работе способ вычисления нижней оценки индекса роста. Оказывается, пара шаблонов $(XYX)^2$ и $X^3$ неизбежна над бинарным алфавитом (см. примечание \ref{subsection:xyx_ad}), а пара шаблонов $(XXY)^2$ и $X^3$~--- избегаема, хотя индекс роста для шаблона $(XXY)^2$ меньше, чем для шаблона $(XYX)^2$. 

\begin{table}[!htb]
\caption{\sl Оценки индексов роста языков над бинарным алфавитом, избегающих шаблоны. Обозначения столбцов перечислены перед таблицей \ref{table:exp}.}
\label{table:xxy}

\vspace*{5pt}
\tabcolsep=3pt

\centerline{
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$Pattern$ & $R$ & $|Q|$ & $|M|$ & $|V|$ & $|{V}_{scc}|$ & $\bar{n}$ & $\gamma$ & $\alpha$ \\
\hline
$(XXY)^2$ & 26 & 100\,758\,143 & 2\,595\,854 & 62\,004\,459 & 55\,164\,403 & 154 & --- & 1.779172 \\
\hline
$(XXY)^2+X^3$ & 126 & 620\,879\,761 & 592\,623 & 74\,794\,781 & 13\,332\,148 & 1559 & 1.098814 & 1.098891 \\
\hline
$(XYX)^2$ & 26 & 263\,913\,221 & 2\,270\,133 & 57\,291\,035 & 33\,452\,876 & 100 & --- & 1.816274 \\
\hline
\end{tabular}
}
\end{table}

\newpage
\section{Заключение}
\label{section:final}

В работе был рассмотрен алгоритм вычисления оценок индексов роста для некоторых нерегулярных языков, в частности, для языков, избегающих экспоненту, и языков над бинарным алфавитом, избегающих некоторые шаблоны. Рассмотрены различные модификации и оптимизации этих алгоритмов, позволяющие существенно сократить время работы и объем используемой памяти. Программа, выполняющая этот алгоритм, была реализована на практике.

Написанная программа позволяет с достаточно высокой точностью вычислять оценки даже на обычном домашнем компьютере. В результате компьютерных исследований были обнаружены различные закономерности: единственность и примитивность компоненты сильной связности распознающих автоматов, рост её размера с ростом экспоненты, найден предполагаемый вид точек, в которых индекс роста имеет большой скачок. Были также вычислены верхняя и нижняя оценки индекса роста языка, избегающего пару шаблонов $(XXY)^2$ и $X^3$. Показана неизбежность пары шаблонов $(XYX)^2$ и $X^3$ над бинарным алфавитом.

Рассмотренные оптимизации могут быть полезными для изучения других аспектов, связанных с комбинаторикой слов в целом и работой с большими автоматами в частности. Написанная программа легко модифицируется для вычисления индексов роста многих других языков, задаваемых антисловарём.

\newpage
\section{Библиография}
\begin{thebibliography}{99}

\bibitem{aho}
Aho A.V. Efficient string matching: An aid to bibliographic search / A.V. Aho, M.J. Corasick // Communications of the ACM. - 1975. - V. 18(6). - p. 333-340.

\bibitem{godsil}
Godsil C.D. Algebraic combinatorics / C.D. Godsil. - New York: Chapman and Hall, 1993. - 368 p.

\bibitem{shur_algo}
Shur A.M. Growth rates of complexity of power-free languages / A.M. Shur // submitted to Theor. Comp. Sci. - 2008.

\bibitem{shur_lower}
Shur A.M. Two-sided bounds for the growth rates of power-free languages. / A.M. Shur // V. Diekert and D. Nowotka (Eds.): DLT 2009, Lect. Notes Comp. Sci. - 2009. - V. 5583. - p. 466–477.

\bibitem{tarjan}
Tarjan R. Depth-first search and linear graph algorithms. / R. Tarjan // SIAM Journal on Computing. - 1972. - V. 1, No. 2. - p. 146-160.

\bibitem{thue}
Thue A. \"Uber unendliche Zeichenreihen. / A. Thue // Kra. Vidensk. Selsk. Skrifter. I. Mat.–Nat. Kl. – 1906. – V. 7. – p. 1–22.

\end{thebibliography}



\newpage
\section{Приложения}
\label{section:aux}
\subsection{Вспомогательные функции (антисловарь)}
\label{subsection:aux_ad}
\begin{verbatim}
char phi[ALPH_SIZE]; //биекция для перевода в лексмин-эквивалент

// Проверяемое слово длины len записано в массиве buff
// dir=1 - чтение слева направо, dir=-1 - чтение справа налево
bool forbidden(const char * buff, int len, char dir){
  int cv = 1; // корень бора
  int cur = 0; // количество разных букв в проверяемом слове
  int sp, fp;
  if (dir > 0){
    sp = 0;
    fp = len;
  }
  else{
    sp = len-1;
    fp = -1;
  }
  memset(phi, 0xFF, sizeof(phi)); // биекция неопределена
  for (int i=sp; i!=fp; i+=dir){
    if (bij[buff[i]] < 0){ // значение не определено
      bij[buff[i]] = cur; // ставим минимально возможное значение
      cur++;
    }
    char c = bij[buff[i]];
    int zv = dfa[cv * ALPH_SIZE + c]; // переход по бору
    if (!zv) return false; // такого ребра в боре нет
    if (zv < 0) return true; // слово запрещено
    cv = zv;
  }
  return false;
}

// Добавление слова в бор
void add_word(const char * word, int len){
  int cv = 1; // корень бора
  words_num++;
  for (int i=0; i<len-1; i++){
    char c = word[i];
    if (!dfa[cv*ALPH_SIZE + c]){ // такого ребра нет
      total++; // создаем новую вершину
      dfa[cv*ALPH_SIZE + c] = total;
    }
    cv = dfa[cv*ALPH_SIZE + c]; // переход по бору
  }
  dfa[cv*ALPH_SIZE + word[len-1]] = -1; // запрещаем слово
}
\end{verbatim}



\newpage
\subsection{Пример битового кодирования (очередь)}
\label{subsection:bit_queue}
\begin{verbatim}
const char LONG_MASK = 0x0F; // Маска для хранения 2 букв в байте
const char SHORT_MASK = 0x03; // Маска для хранения 4 букв в байте
bool use_long_mask = (ALPH_SIZE > 4); // Режим кодирования

char words_queue = new char [QUEUE_SIZE];
long long qbeg = 0, qend = 0; // Начало и конец очереди

// Увеличение индекса в циклической очереди
void queue_increase_index(long long &i){
  i++;
  if (use_long_mask){
    if ((i>>1) >= QUEUE_SIZE) i = 0;
  }
  else{
    if ((i>>2) >= QUEUE_SIZE) i = 0;
  }
}

// Добавление символа в конец очереди
void queue_push_symbol(char ch){
  if (use_long_mask){
    int mod = (int)(qend&1);
    words_queue[qend>>1] &= ~(LONG_MASK << (4*mod));
    words_queue[qend>>1] |= (ch << (4*mod));
  }
  else{
    int mod = (int)(qend&3);
    words_queue[qend>>2] &= ~(SHORT_MASK << (2*mod));
    words_queue[qend>>2] |= (ch << (2*mod));
  }
  queue_increase_index(qend);
}

// Получение символа из очереди
char qbeg_peek_symbol(){
  if (use_long_mask){
    int mod = (int)(qbeg&1);
    return (words_queue[qbeg>>1] & (LONG_MASK<<(4*mod)))>>(4*mod);
  }
  else{
    int mod = (int)(qbeg&3);
    return (words_queue[qbeg>>2] & (SHORT_MASK<<(2*mod)))>>(2*mod);
  }
}
\end{verbatim}



\newpage
\subsection{Поиск вершины из компоненты сильной связности}
\label{subsection:dfs_tarjan}
\begin{verbatim}
father[v] - отец v в дереве поиска в глубину;
nxt_used[v] хранит следующую информацию:
первые 4 бита - количество обработанных соседей v
5-й бит - обработка вершины v начата, но не закончена
6-й бит - вершина v посещена
исходно массивы заполены нулями

const char LONG_MASK = 0x0F;

void find_vertex_in_cycle(){
  father[1] = 0;
  nxt_used[1] ^= 32; // начинаем поиск из первой вершины
  int cver = 1, cedge, nver;
  while (cver > 0){
    cedge = nxt_used[cver] & LONG_MASK;
    if (cedge == 0){  // обрабатываем первого соседа вершины
      nxt_used[cver] ^= 16;
    }
    if (cedge >= ALPH_SIZE){ // соседи обработаны, переходим к отцу
      nxt_used[cver] ^= 16;
      cver = father[cver];
      continue;
    }
    nxt_used[cver]++;
    nver = dfa[cver*ALPH_SIZE + cedge]; // номер очередного соседа
    if (!nver) continue; // ребра может не существовать
    if ((nxt_used[nver] & 32) == 0){ // переходим в новую вершину
      father[nver] = cver;
      nxt_used[nver] ^= 32;
      cver = nver;
    }
    else if (nxt_used[nver] & 16){ // возвратное ребро даёт цикл
      vert_incycle = nver;
    }
  }
}
\end{verbatim}



\newpage
\subsection{Антисловарь для пары шаблонов $(XYX)^2$ и $X^3$}
\label{subsection:xyx_ad}
\begin{verbatim}
aaa
aabbababbaabaabbababbaab
aabbababbaababaabbabbaabaabbababbaababaabbabbaab
aabbabbaabaabbabbaab
aabbabbaababaabbababbaabaabbabbaababaabbababbaab
abaaba
abaabbababbaabaabbababba
abaabbababbaabaabbabbaababaabbababbaabaabbabbaab
abaabbababbaababaabbababbaab
abaabbababbaababaabbabbaabaabbababbaababaabbabba
abaabbabbaabaabbababbaababaabbabbaabaabbababbaab
abaabbabbaabaabbabba
abaabbabbaababaabbababbaabaabbabbaababaabbababba
abaabbabbaababaabbabbaab
ababaabbababbaabaabbabbaababaabbababbaabaabbabba
ababaabbababbaababaabbababba
ababaabbabbaabaabbababbaababaabbabbaabaabbababba
ababaabbabbaababaabbabba
ababab
ababbaababba
abbaababbaab
abbaabba
\end{verbatim}

\end{document}
